package main.Q101_200;

import java.util.*;

public class Q151_160 {
    public static void main(String[] args) {
        System.out.println("Question151：反转字符串中的单词");
        System.out.println("Question152：乘积最大子数组");
        System.out.println("Question153：寻找旋转排序数组中的最小值");
        System.out.println("Question154：寻找旋转排序数组中的最小值Ⅱ");
        System.out.println("Question155：最小栈");
        System.out.println("Question156：");
        System.out.println("Question157：");
        System.out.println("Question158：");
        System.out.println("Question159：");
        System.out.println("Question160：相交链表");
    }
}

class Question151{
    public String reverseWords(String s) {
        StringBuffer reverse=new StringBuffer();
        List<String> strList=new ArrayList<>();
        char[] str=s.toCharArray();
        for (int i=0;i< str.length;){//将单词存入
            if (str[i]!=' '){//开始不为空格时
                StringBuffer temp=new StringBuffer();
                int j=i;
                while (j< str.length&&str[j]!=' '){
                    temp.append(str[j]);
                    j++;
                }
                strList.add(temp.toString());
                i=j;
            }else i++;
        }
        for (int i=strList.size()-1;i>0;i--){
            reverse.append(strList.get(i));
            reverse.append(' ');
        }
        reverse.append(strList.get(0));
        return reverse.toString();
    }
}

class Question152{
    public int maxProduct(int[] nums) {//动态规划表
        int max=Integer.MIN_VALUE;
        int[] dp=new int[nums.length];
        for (int i=0;i< nums.length;i++){
            dp[i]=nums[i];
            max=Math.max(max,dp[i]);
            for (int j=i+1;j< nums.length;j++){
                dp[j]=dp[j-1]*nums[j];
                max=Math.max(max,dp[j]);
            }
        }
        return max;
    }
}

class Question153{
    public int findMin(int[] nums) {
        int left=0,right= nums.length-1;
        while (left<right){
            int mid=(left+right)/2;
            if (nums[mid]<nums[right]) right=mid;
            else left=mid+1;
        }
        return nums[left];
    }
}

class Question154{
    public int findMin(int[] nums) {
        int min=Integer.MAX_VALUE;
        for (int num:nums) min=Math.min(num,min);
        return min;
    }
}

class Question155{//设置一个辅助栈，只存最小值
    Stack<Integer> stack;
    Stack<Integer> assStack;
    public Question155() {
        this.stack=new Stack<>();
        this.assStack=new Stack<>();
        assStack.add(Integer.MAX_VALUE);
    }

    public void push(int val) {
        int min=assStack.peek();//辅助栈中的栈顶元素，即是当前栈中最小值
        if (val<min) assStack.add(val);//入栈元素小于最小元素，则辅助栈中压入val
        else assStack.add(min);//反之再次压入最小元素
        stack.add(val);
    }

    public void pop() {
        stack.pop();
        assStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return assStack.peek();
    }
//哈希表及有序表解决
//    Stack<Integer> stack;
//    TreeSet<Integer> set;
//    Map<Integer,Integer> map;
//    public MinStack() {
//        this.stack=new Stack<>();
//        this.set=new TreeSet<>();
//        this.map=new HashMap<>();
//    }
//
//    public void push(int val) {
//        stack.add(val);
//        map.put(val,map.getOrDefault(val,0)+1);//记录该元素在栈中出现次数
//        set.add(val);
//    }
//
//    public void pop() {
//        int val=stack.pop();
//        int count=map.get(val);
//        if (count==1) {//出栈元素在栈中是否只有一个
//            map.remove(val);
//            set.remove(val);
//        }else map.put(val,count-1);
//    }
//
//    public int top() {
//        return stack.peek();
//    }
//
//    public int getMin() {
//        return set.first();
//    }
}

class Question160{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}